Correction du Sujet 03 - NSI 2025

Exercice 1 : Justification de texte et programmation dynamique

Partie A

1) Nombre d'espaces nécessaires
Les quatre mots sont An, algorithm, must et be.
Le nombre total de lettres est : 2 + 9 + 4 + 2 = 17.
Pour obtenir une ligne de 25 caractères, il faut donc ajouter : 25 - 17 = 8 espaces.
Il faut donc 8 espaces au total.
2) Répartition correcte des espaces
Il y a 4 mots, donc 3 emplacements entre les mots. On répartit 8 espaces entre ces 3 emplacements :
8 = 3 × 2 + 2.
On place donc 3 espaces dans les deux premiers emplacements et 2 espaces dans le dernier.
La bonne proposition est donc : 
An---algorithm---must--be
3) Précondition de la fonction ajout_espace
Pour que les mots tiennent sur une ligne, il faut que la somme des longueurs des mots, augmentée des espaces minimales entre deux mots, ne dépasse pas la justification. 
5     assert nb_caracteres + nb_mots - 1 <= justification
4) Complétion des lignes 8, 14 et 17
8         return liste_mots[0] + " " * nb_espace_total
14            reponse = reponse + " " * (q + 1) \
15            + liste_mots[i]
17            reponse = reponse + " " * q \
18            + liste_mots[i]

Partie B

5) Algorithme naturel pour choisir les retours à la ligne
On parcourt les mots dans l'ordre. On commence une ligne avec le premier mot disponible, puis on ajoute le mot suivant tant que la ligne obtenue ne dépasse pas la justification, en comptant une espace minimale entre deux mots. Dès que le mot suivant ne tient plus, on revient à la ligne avant ce mot. On recommence de la même manière jusqu'à avoir placé tous les mots.
6) Complétion de la fonction affiche_justifie
def affiche_justifie(liste_mots: list[str], decoupage: list[(int, int)], justification: int) -> None:
    for a, b in decoupage:
        ligne_justifiee = ajout_espace(liste_mots[a:b], justification)
        print(ligne_justifiee)

Partie C

7) Complétion du tableau des coûts
Indice du mot de début Indice du mot de fin + 1 Nombre de mots Nombre de caractères Nombre d'espaces supplémentaires Coût
0221139
2426864
4738525
7818749
Le coût total vaut bien : 9 + 64 + 25 + 49 = 147.
8) Fonction cout
def cout(i, j, liste_mots, justification):
    nb_mots = j - i
    nb_caracteres = 0
    for k in range(i, j):
        nb_caracteres = nb_caracteres + len(liste_mots[k])
    nb_min = nb_caracteres + nb_mots - 1
    if nb_min > justification:
        return 1000000
    nb_espaces_supplementaires = justification - nb_min
    return nb_espaces_supplementaires ** 2
9) Recherche exhaustive
Pour une liste de n mots, on peut choisir de revenir ou non à la ligne après chacun des n - 1 premiers mots. Cela donne 2^(n-1) possibilités.
Pour n ≥ 50, ce nombre est beaucoup trop grand. Il n'est donc pas raisonnable de tester tous les découpages possibles.
10) Nombre d'appels à la fonction cout
La fonction cout est appelée une fois pour chaque valeur de i, puis dans la boucle interne pour chaque couple (i, j) avec i < j.
Le nombre total d'appels est de l'ordre de : 
n + n(n - 1) / 2
L'ordre de grandeur est donc quadratique, c'est-à-dire O(n²).
11) Relation entre les éléments de cout_mini
Pour chaque indice i, cout_mini[i] contient le coût minimal pour justifier le texte depuis le mot d'indice i jusqu'au dernier mot.
La relation est : 
cout_mini[i] = min(cout(i, n), cout(i, j) + cout_mini[j])
où j parcourt les indices de i + 1 à n - 1.
12) Modification pour renvoyer aussi le coût
Il suffit de renvoyer aussi cout_mini[0], qui contient le coût minimal pour justifier tout le texte. 
return decoupage, cout_mini[0]

Exercice 2 : Arbres binaires et codage de Huffman

1) Exemple de feuille et racine
Un exemple de feuille est le nœud (j,1).
La racine est le nœud contenant tous les caractères de la phrase, de poids total 19 : ( -j-f-e-l-i-p-t-a-u,19).
2) Profondeur et code du caractère p
Pour atteindre le caractère p, on suit le chemin : droite, droite, gauche, gauche.
Le code associé est donc : 1100.
Ce chemin contient 4 arêtes, donc la profondeur du nœud p est 4.
3) Intérêt de placer les caractères fréquents près de la racine
Un caractère placé à faible profondeur possède un code binaire plus court. Comme les caractères fréquents apparaissent souvent, leur attribuer un code court permet de réduire la taille totale du texte compressé.
4) Complétion de la classe Noeud
class Noeud:
    def __init__(self, nom, nb_occu, fils_g, fils_d):
        self.nom = nom
        self.nb_occu = nb_occu
        self.fils_g = fils_g
        self.fils_d = fils_d

    def __str__(self):
        return '(' + self.nom + ',' + str(self.nb_occu) + ')'
5) Fonction liste_occurrences
def liste_occurrences(chaine):
    dico = {}
    for c in chaine:
        if c in dico:
            dico[c] = dico[c] + 1
        else:
            dico[c] = 1
    liste_res = []
    for cle in dico:
        liste_res.append((cle, dico[cle]))
    return liste_res
6) Fonction tri_liste
def tri_liste(liste_a_trier):
    liste_triee = []
    for i in range(0, len(liste_a_trier)):
        element = liste_a_trier[i]
        j = 0
        while j < len(liste_triee) and element[1] >= liste_triee[j][1]:
            j = j + 1
        liste_triee.insert(j, element)
    return liste_triee
7) Fonction conversion_en_noeuds
def conversion_en_noeuds(liste):
    liste_noeuds = []
    for caractere, nb_occu in liste:
        liste_noeuds.append(Noeud(caractere, nb_occu, None, None))
    return liste_noeuds
8) Fonction insere_noeud
def insere_noeud(noeud, liste_noeud):
    j = 0
    while j < len(liste_noeud) and noeud.nb_occu > liste_noeud[j].nb_occu:
        j = j + 1
    liste_noeud.insert(j, noeud)
9) Fonction construit_arbre
def construit_arbre(liste):
    while len(liste) > 1:
        noeud1 = liste.pop(0)
        noeud2 = liste.pop(0)
        nom_noeud_pere = noeud1.nom + "-" + noeud2.nom
        nb_occu_noeud_pere = noeud1.nb_occu + noeud2.nb_occu
        noeud_pere = Noeud(nom_noeud_pere, nb_occu_noeud_pere, noeud1, noeud2)
        insere_noeud(noeud_pere, liste)
    return liste[0]
10) Structure de données renvoyée par codage_arbre
La structure obtenue est un dictionnaire. Les clés sont les caractères, et les valeurs sont les codes binaires associés.
11) Fonction compresse
def compresse(texte, codage):
    resultat = ""
    for caractere in texte:
        resultat = resultat + codage[caractere]
    return resultat

Exercice 3 : Graphes, programmation objet et bases de données

Partie A

1) Modification de la durée de la grande roue
a4.duree = 12
2) Valeur de a2.voisines[2][1]
a2.voisines[2] vaut (a4, 4). Donc a2.voisines[2][1] vaut 4.
Cette valeur correspond à la durée du trajet entre a2, les Petits chevaux, et a4, la Grande roue.
3) Explication de la ligne 7
La ligne 7 indique que l'attraction a3, c'est-à-dire le Train fantôme, est voisine de trois attractions : le Grand huit en 5 minutes, les Petits chevaux en 3 minutes et la Grande roue en 6 minutes.
4) Complétion de la ligne 8
a4.voisines = [(a2, 4), (a3, 6)]
5) Graphe non orienté
Le graphe est non orienté car les déplacements entre attractions peuvent se faire dans les deux sens. Si l'on peut aller d'une attraction A à une attraction B, on peut aussi revenir de B vers A par le même chemin.
6) Durée de la balade [a1, a2, a3]
On additionne les durées des attractions et les durées des trajets entre attractions successives :
11 + 7 + 6 + 3 + 9 = 36.
La durée totale de la balade est donc de 36 minutes.
7) Pourquoi [a2, a1, a4, a3] n'est pas une balade
Pour que ce tableau soit une balade, chaque attraction devrait être voisine de la suivante. Or a1, le Grand huit, n'est pas voisin de a4, la Grande roue. Le trajet a1 → a4 n'existe pas dans le graphe.
8) Fonction sont_voisines
def sont_voisines(attraction1, attraction2):
    for voisine, duree in attraction1.voisines:
        if voisine == attraction2:
            return True
    return False
9) Fonction est_balade
def est_balade(tab):
    for i in range(len(tab) - 1):
        if not sont_voisines(tab[i], tab[i + 1]):
            return False
    return True
10) Type de parcours effectué
La fonction effectue un parcours en profondeur, car elle explore récursivement chaque voisin avant de revenir explorer les voisins suivants.
11) Contenu de balade après l'appel parcours(a4, {}, balade, 0)
En partant de a4, l'ordre obtenu est : a4, puis a2, puis a1, puis a3.
Le tableau vaut donc : 
[a4, a2, a1, a3]
12) Contenu de tableau après le second appel
Avec les voisinages modifiés, l'appel à partir de a3 place successivement a3, a1, puis a2. L'attraction a4 est visitée, mais elle n'est pas ajoutée car elle n'est pas voisine de la dernière attraction placée, qui est a2.
Le tableau vaut donc : 
[a3, a1, a2, None]
13) Structure de données utilisée pour deja_vues
La variable deja_vues est un dictionnaire. Elle associe le nom de chaque attraction déjà visitée à la valeur True, ce qui évite de traiter plusieurs fois la même attraction.

Partie B

14) Clé primaire et clé étrangère
Une clé primaire est un attribut, ou un ensemble d'attributs, qui permet d'identifier de manière unique chaque ligne d'une table.
Une clé étrangère est un attribut qui référence la clé primaire d'une autre table. Elle permet de relier les tables et de garantir la cohérence des données.
15) Visiteurs présents le 11 janvier 2025 sans doublons
SELECT DISTINCT nom, prenom
FROM visiteur
WHERE date = '2025-01-11';
16) Somme payée par Alan TURING en 2024
SELECT SUM(photo.prix)
FROM visiteur
JOIN photo ON visiteur.id = photo.id_visiteur
WHERE visiteur.nom = 'TURING'
AND visiteur.prenom = 'Alan'
AND visiteur.date >= '2024-01-01'
AND visiteur.date < '2025-01-01';
17) Interprétation de la requête
La requête cherche les noms et prénoms des visiteurs ayant été photographiés dans l'attraction Grande roue, à 12:34, le 26 juillet 2024.
18) Modification de la base pour plusieurs formats et supports
Il est préférable de ne plus stocker un seul prix directement dans la table photo, car une même photo peut désormais être vendue sous plusieurs formes.
On peut ajouter une table des produits proposés et une table d'association entre les photos et ces produits : 
visiteur(id, nom, prenom, date)
attraction(id, nom, duree)
photo(id, id_visiteur, id_attraction, heure)
produit(id_produit, libelle, prix)
vente(id_photo, id_produit)
La table produit peut contenir par exemple A5, A6, poster ou porte-clé, avec le prix correspondant. La table vente indique quels produits ont été achetés pour une photo donnée.